1. Field
Embodiments disclosed herein generally relate to job scheduling and in particular, but not exclusively, to backfill job scheduling.
2. Background
The process whereby a group of jobs is scheduled for execution in a computing environment according to a scheduling algorithm is generally referred to as batch scheduling. The most basic batch scheduling algorithm is the First-Come-First-Served (FCFS) scheduling algorithm. With this algorithm, jobs are placed in a First In, First Out (FIFO) queue upon arrival. If there are sufficient resources available to run the job at the head of the queue, the resources are allocated and the job is started. If there are insufficient resources, the process waits until sufficient resources become available, for example when a currently running job terminates. However, this approach suffers from inefficient system utilization.
Backfilling is an optimization technique that tries to balance the goals of utilization and maintaining FCFS order. While the job at the head of the queue is waiting, it is possible for other, smaller jobs, to be scheduled, especially if they would not delay the start of the job on the head of the queue. This allows resources, which would otherwise remain unused, to be used. Backfill scheduling generally requires users to specify runtime limits for their jobs in order to enable a scheduler to determine where to place the jobs. However, because jobs that execute beyond their specified runtime are usually terminated by the system, users will often overestimate the runtime of their jobs. This leads to scheduling inefficiencies and wasted resources.
Hence, improved job scheduling techniques would be well received in the computing industry.